public class Solution10 {
    /*    public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
            for (int i = 0; i < dp.length; i++) {
                boolean[] booleans = dp[i];
                for (int j = 0; j < booleans.length; j++) {
                    dp[i][j] = false;
                }
            }

            char[] str = s.toCharArray();
            char[] m = p.toCharArray();
            dp[0][0] = true;
            dp[1][1] = m[0] == str[0] || m[0] == '.';
            for (int i = 2; i < m.length + 1; i++) {
                for (int j = 0; j < str.length + 1; j++) {
                    if (j > 0 && (m[i - 1] == str[j - 1] || m[i - 1] == '.')) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (m[i - 1] == '*') {
                        dp[i][j] = ((j > 0 && (dp[i - 1][j - 1] || dp[i][j - 1])) && (m[i - 2] == '.' || m[i - 2] == str[j - 1]))    //*作为一个字符匹配
                                || dp[i - 1][j]     //*作为0个字符匹配
                                || dp[i - 2][j];    //*和前一个字符一起作为0个字符匹配
                    }
                }
            }

            return dp[m.length][str.length];
        }*/
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = matches(s, p, i, j) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    private boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}
